package com.zjj.algorithm.learning.atguigu.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 将中缀表达式转化为后缀表达式
 *
 * @author zjj_admin
 * @date 2022/11/9 19:37
 */
public class InfixToSuffix {

    public static void main(String[] args) {
        String infixExpr = "12+((2+32)*4)-5";
        List<String> infixExprList = toInfixExpr(infixExpr);
        System.out.println("infixExprList = " + infixExprList);
        //将中缀表达式对应的list转化为后缀表达式对应的list
        List<String> suffixExpr = parseInfixExprToSuffix(infixExprList);
        System.out.println("suffixExpr = " + suffixExpr);
        int res = PolandNotation.calculate(suffixExpr);
        System.out.println("res = " + res);
    }


    /**
     * 1+((2+3)×4)-5 转 "1 2 3 + 4 × + 5 –"
     * <p>
     * 1、初始化两个栈：运算符栈s1和储存中间结果的栈s2；
     * 2、从左至右扫描中缀表达式；
     * 3、遇到操作数时，将其压s2
     * 4、遇到运算符时，比较其与s1栈顶运算符的优先级：
     * (1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
     * (2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；
     * (3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4、(1)步骤)与s1中新的栈顶运算符相比较；
     * 5、遇到括号时：
     * (1) 如果是左括号“(”，则直接压入s1
     * (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
     * 5、重复步骤2至5，直到表达式的最右边
     * 7、将s1中剩余的运算符依次弹出并压入s2
     * 8、依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
     *
     * @param ls
     * @return
     */
    public static List<String> parseInfixExprToSuffix(List<String> ls) {

        //定义两个栈 s1 和 s2，一个栈用于存放运算符，另一个栈用于存放转化的数据
        //考虑到存放后缀表达式的栈没有出栈操作，并且结果需要逆序则可以使用 List 来代替
        Stack<String> s1 = new Stack<>();
        List<String> s2 = new ArrayList<>();
        for (String item : ls) {
            //若为数字 0 - 9 就直接如 s2
            if (item.matches("\\d+")) {
                s2.add(item);
                //当匹配到 '(' 时，直接 入 s1
            } else if ("(".equals(item)) {
                s1.push(item);
            } else if (")".equals(item)) {
                //当匹配到 ')' 时，依次弹出 s1 中的运算符，指导遇到 '('
                while (!"(".equals(s1.peek())) {
                    s2.add(s1.pop());
                }
                //将 '(' 丢弃
                s1.pop();

            } else {
                //当匹配的是运算符时
                //当当前的运算符的优先级 小于等于 s1 栈顶 运算符的优先级时，将 s1 中的运算符弹出，并加入到 s2中
                if(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){
                    s2.add(s1.pop());
                }
                //同时将 当前运算符压入 s1 中
                s1.push(item);
            }

        }
        //循环以后将 s1 中的运算符依次全部加入到 s2 中
        while (s1.size() > 0){
            s2.add(s1.pop());
        }

        return s2;
    }


    /**
     * 将中缀表达式对应的字符串转化为list
     *
     * @param infixExpr
     * @return
     */
    public static List<String> toInfixExpr(String infixExpr) {
        infixExpr = infixExpr.trim();
        List<String> list = new ArrayList<>();
        int index = 0;
        //拼接多位数，当出现 25- 时，需要将 25 看做一个整体
        String str;
        //每一次遍历的字符
        char c;
        do {
            c = infixExpr.charAt(index);
            //当符号是字符时，就直接加入
            if ((c < '0' || c > '9')) {
                list.add(c + "");
                index++;
            } else {
                str = "";
                //方符号是数字时，需要判断后面是否跟着数字
                while (
                        index < infixExpr.length()
                                && infixExpr.charAt(index) >= '0'
                                && (c = infixExpr.charAt(index)) <= '9'
                ) {
                    str += c;
                    index++;

                }
                list.add(str);
            }
        } while (index < infixExpr.length());
        return list;
    }
}

class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    /**
     * 写一个方法，返回对应的优先级数字
     * @param operation
     * @return
     */
    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在该运算符" + operation);
                break;
        }
        return result;
    }
}



